#include<vector>
#include<map>
#include<algorithm>
using namespace std;


// vector<int> cur(nums.begin() + i, nums.end()); 切片
// 未解决重复的问题
class Solution {
public:
    vector<int> twoSum(vector<int> nums, int target) {
        map<int, int> mp;
        int n = nums.size();

        for (int i = 0; i < n; i ++) {
            if (mp[target - nums[i]] == 0) {
                // nums[i]为第i+1个元素
                mp[nums[i]] = i + 1;
            }else{
                int idx = mp[target - nums[i]];
                return vector<int> {nums[idx - 1], nums[i]};
            }
        }

        return {};
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();

        vector<vector<int>> ans;
        vector<int> cur_ans;
        for (int i = 0; i < n; i++) {
            // vector<int> cur = nums(nums.begin() + i, nums.end());
            vector<int> cur(nums.begin() + i, nums.end());
            cur_ans = twoSum(cur, (0 - nums[i]));

            if (cur_ans.size() == 0) continue;
            cur_ans.push_back(nums[i]);
            ans.push_back(cur_ans);
            cur_ans.clear();
        }

        return ans;
    }
};